{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "# `Nuqleon.Memory`\n",
        "\n",
        "Provides object pools, function memoization, and caching utilities."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Reference the library"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Option 1 - Use a local build\n",
        "\n",
        "If you have built the library locally, run the following cell to load the latest build."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "#r \"bin/Debug/net6.0/Nuqleon.Memory.dll\""
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Option 2 - Use NuGet packages\n",
        "\n",
        "If you want to use the latest published package from NuGet, run the following cell."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "#r \"nuget:Nuqleon.Memory,*-*\""
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## (Optional) Attach a debugger\n",
        "\n",
        "If you'd like to step through the source code of the library while running samples, run the following cell, and follow instructions to start a debugger (e.g. Visual Studio). Navigate to the source code of the library to set breakpoints."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "System.Diagnostics.Debugger.Launch();"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Using object pools\n",
        "\n",
        "Object pools can be used to reduce the overhead of allocating fresh objects. This library supports object pooling for arbitrary types but also have built-in support for commonly used types, such as `StringBuilder` and various collection types."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Using an object pool for a well-known collection type\n",
        "\n",
        "First, we'll explore support for built-in types by having a look at pooling for `Stack<T>` objects. Support for other types is completely analogous."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "#### Step 1 - Create a pool\n",
        "\n",
        "The first step is to create a pool using one of the `Create` static method overloads on the pool type. In this example, we'll use `StackPool<T>` and create a pool that can grow up to `8` instances."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "var pool = StackPool<int>.Create(size: 8);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "#### Step 2 - Inspect the pool using `DebugView`\n",
        "\n",
        "At any time we can have a look at the pool's internals using the `DebugView` property. This shows statistics of the pool, as well as call stacks for allocations and deallocations in `DEBUG` builds.\n",
        "\n",
        "**Note:** Because the `DebugView` contains quite lengthy stack traces due to invocations taking place in .NET Interactive underneath the Notebook, we use a simple helper function to trim stack traces below. In regular use cases outside Notebooks, `DebugView` is typically accessed in the Visual Studio debugger Watch window."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "System.Collections.Generic.StackPool`1+Impl0[System.Int32] : ObjectPoolBase<System.Collections.Generic.PooledStack`1[System.Int32]>\r\n===================================================================================================================================\r\n\r\nCreation trace\r\n--------------\r\n\r\n21/03/04 16:58:31.3985714 [00:00:01.6164524 ago] @ ~13 () in 1 (Microsoft.DotNet.Interactive.App)\r\n   at System.Memory.ObjectPoolBase`1..ctor(Int32 size)\r\n   at System.Collections.Generic.StackPool`1..ctor(Int32 size)\r\n   at System.Collections.Generic.StackPool`1.Impl0..ctor(Int32 size)\r\n   at System.Collections.Generic.StackPool`1.Create(Int32 size)\r\n   at <Notebook>\r\n\r\n\r\nStatistics\r\n----------\r\n\r\n  # slots:   8\r\n  # standby: 0\r\n  # allocs:  0\r\n  # frees:   0\r\n  # create:  0\r\n  # drops:   0\r\n\r\n\r\nPool entries\r\n------------\r\n\r\n  [0] = <empty>\r\n  [1] = <empty>\r\n  [2] = <empty>\r\n  [3] = <empty>\r\n  [4] = <empty>\r\n  [5] = <empty>\r\n  [6] = <empty>\r\n  [7] = <empty>\r\n\r\n\r\nTracked objects\r\n---------------\r\n\r\n\r\n\r\n\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "using System.IO;\n",
        "using System.Text.RegularExpressions;\n",
        "\n",
        "// Regular expression to match stack trace lines with any amount of leading whitespace.\n",
        "var isStackTraceLine = new Regex(\"^([ \\t]*)at (.*)$\");\n",
        "\n",
        "// Eat our own object pooling dogfood here as well :-).\n",
        "var stringBuilderPool = StringBuilderPool.Create(size: 8);\n",
        "\n",
        "string TrimDebugView(string debugView)\n",
        "{\n",
        "    using (var sb = stringBuilderPool.New())\n",
        "    using (var sr = new StringReader(debugView))\n",
        "    {\n",
        "        var skip = false;\n",
        "        string line;\n",
        "\n",
        "        while ((line = sr.ReadLine()) != null)\n",
        "        {\n",
        "            var match = isStackTraceLine.Match(line);\n",
        "\n",
        "            if (skip && !match.Success)\n",
        "            {\n",
        "                skip = false;\n",
        "            }\n",
        "\n",
        "            if (!skip)\n",
        "            {\n",
        "                if (match.Success && match.Groups[2].Value.StartsWith(\"Submission\"))\n",
        "                {\n",
        "                    sb.StringBuilder.AppendLine(match.Groups[1].Value + \"at <Notebook>\");\n",
        "                    skip = true;\n",
        "                }\n",
        "                else\n",
        "                {\n",
        "                    sb.StringBuilder.AppendLine(line);\n",
        "                }\n",
        "            }\n",
        "        }\n",
        "\n",
        "        return sb.StringBuilder.ToString();\n",
        "    }\n",
        "}\n",
        "\n",
        "void PrintDebugView()\n",
        "{\n",
        "    Console.WriteLine(TrimDebugView(pool.DebugView));\n",
        "}\n",
        "\n",
        "PrintDebugView();\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "#### Step 3 - Allocate an object from the pool\n",
        "\n",
        "One way to allocate an object from the pool is by using `Allocate`. Once we're done using the object, we call `Free`. This is typically done in a safe manner, e.g. using a `try...finally...` statement. In case an object is not returned to the pool, it will just get garbage collected and the pool's performance will be degraded. However, there won't be a memory leak."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "System.Collections.Generic.StackPool`1+Impl0[System.Int32] : ObjectPoolBase<System.Collections.Generic.PooledStack`1[System.Int32]>\r\n===================================================================================================================================\r\n\r\nCreation trace\r\n--------------\r\n\r\n21/03/04 16:58:31.3985714 [00:00:08.3823493 ago] @ ~13 () in 1 (Microsoft.DotNet.Interactive.App)\r\n   at System.Memory.ObjectPoolBase`1..ctor(Int32 size)\r\n   at System.Collections.Generic.StackPool`1..ctor(Int32 size)\r\n   at System.Collections.Generic.StackPool`1.Impl0..ctor(Int32 size)\r\n   at System.Collections.Generic.StackPool`1.Create(Int32 size)\r\n   at <Notebook>\r\n\r\n\r\nStatistics\r\n----------\r\n\r\n  # slots:   8\r\n  # standby: 0\r\n  # allocs:  1\r\n  # frees:   0\r\n  # create:  1\r\n  # drops:   0\r\n\r\n\r\nPool entries\r\n------------\r\n\r\n  [0] = <empty>\r\n  [1] = <empty>\r\n  [2] = <empty>\r\n  [3] = <empty>\r\n  [4] = <empty>\r\n  [5] = <empty>\r\n  [6] = <empty>\r\n  [7] = <empty>\r\n\r\n\r\nTracked objects\r\n---------------\r\n\r\n  #1 - checked out\r\n  \r\n    Stats\r\n    ~~~~~\r\n\r\n      Usage count =  0\r\n      \r\n    History\r\n    ~~~~~~~\r\n\r\n      Alloc - 21/03/04 16:58:39.7808835 [00:00:00.0080656 ago] @ ~4 () in 1 (Microsoft.DotNet.Interactive.App)\r\n         at System.Memory.ObjectPoolBase`1.Allocate()\r\n         at <Notebook>\r\n      \r\n\r\n\r\n\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "PooledStack<int> stack = pool.Allocate();\n",
        "\n",
        "PrintDebugView();\n",
        "\n",
        "try\n",
        "{\n",
        "    // Use the object here.\n",
        "    stack.Push(1);\n",
        "}\n",
        "finally\n",
        "{\n",
        "    pool.Free(stack);\n",
        "}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Now that we've returned the object back to the pool, let's inspect the pool again."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "System.Collections.Generic.StackPool`1+Impl0[System.Int32] : ObjectPoolBase<System.Collections.Generic.PooledStack`1[System.Int32]>\r\n===================================================================================================================================\r\n\r\nCreation trace\r\n--------------\r\n\r\n21/03/04 16:58:31.3985714 [00:00:15.1071969 ago] @ ~13 () in 1 (Microsoft.DotNet.Interactive.App)\r\n   at System.Memory.ObjectPoolBase`1..ctor(Int32 size)\r\n   at System.Collections.Generic.StackPool`1..ctor(Int32 size)\r\n   at System.Collections.Generic.StackPool`1.Impl0..ctor(Int32 size)\r\n   at System.Collections.Generic.StackPool`1.Create(Int32 size)\r\n   at <Notebook>\r\n\r\n\r\nStatistics\r\n----------\r\n\r\n  # slots:   8\r\n  # standby: 1\r\n  # allocs:  1\r\n  # frees:   1\r\n  # create:  1\r\n  # drops:   0\r\n\r\n  avg use time: 00:00:00.0101310\r\n  max use time: 00:00:00.0101310\r\n\r\n\r\nPool entries\r\n------------\r\n\r\n  [0] = #1\r\n  [1] = <empty>\r\n  [2] = <empty>\r\n  [3] = <empty>\r\n  [4] = <empty>\r\n  [5] = <empty>\r\n  [6] = <empty>\r\n  [7] = <empty>\r\n\r\n\r\nTracked objects\r\n---------------\r\n\r\n  #1 - standby\r\n  \r\n    Stats\r\n    ~~~~~\r\n\r\n      Usage count =  1\r\n      Max use time = 00:00:00.0101310\r\n      Avg use time = 00:00:00.0101310\r\n      \r\n    History\r\n    ~~~~~~~\r\n\r\n      Free  - 21/03/04 16:58:39.7910145 [00:00:06.7154508 ago] @ ~4 () in 1 (Microsoft.DotNet.Interactive.App)\r\n         at System.Memory.ObjectPoolBase`1.Free(T obj)\r\n         at <Notebook>\r\n      Alloc - 21/03/04 16:58:39.7808835 [00:00:06.7261028 ago] @ ~4 () in 1 (Microsoft.DotNet.Interactive.App)\r\n         at System.Memory.ObjectPoolBase`1.Allocate()\r\n         at <Notebook>\r\n      \r\n\r\n\r\n\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "PrintDebugView();"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "#### Step 4 - An alternative way to allocate from the pool\n",
        "\n",
        "An alternative way to allocate an object from the pool is by using `New` which returns a holder object that implements `IDisposable` and can be used with a `using` statement. This makes it easier to ensure returning the object to the pool, even in exceptional circumstances."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "System.Collections.Generic.StackPool`1+Impl0[System.Int32] : ObjectPoolBase<System.Collections.Generic.PooledStack`1[System.Int32]>\r\n===================================================================================================================================\r\n\r\nCreation trace\r\n--------------\r\n\r\n21/03/04 16:58:31.3985714 [00:00:24.0868703 ago] @ ~13 () in 1 (Microsoft.DotNet.Interactive.App)\r\n   at System.Memory.ObjectPoolBase`1..ctor(Int32 size)\r\n   at System.Collections.Generic.StackPool`1..ctor(Int32 size)\r\n   at System.Collections.Generic.StackPool`1.Impl0..ctor(Int32 size)\r\n   at System.Collections.Generic.StackPool`1.Create(Int32 size)\r\n   at <Notebook>\r\n\r\n\r\nStatistics\r\n----------\r\n\r\n  # slots:   8\r\n  # standby: 0\r\n  # allocs:  2\r\n  # frees:   1\r\n  # create:  1\r\n  # drops:   0\r\n\r\n  avg use time: 00:00:00.0101310\r\n  max use time: 00:00:00.0101310\r\n\r\n\r\nPool entries\r\n------------\r\n\r\n  [0] = <empty>\r\n  [1] = <empty>\r\n  [2] = <empty>\r\n  [3] = <empty>\r\n  [4] = <empty>\r\n  [5] = <empty>\r\n  [6] = <empty>\r\n  [7] = <empty>\r\n\r\n\r\nTracked objects\r\n---------------\r\n\r\n  #1 - checked out\r\n  \r\n    Stats\r\n    ~~~~~\r\n\r\n      Usage count =  1\r\n      Max use time = 00:00:00.0101310\r\n      Avg use time = 00:00:00.0101310\r\n      \r\n    History\r\n    ~~~~~~~\r\n\r\n      Alloc - 21/03/04 16:58:55.4852846 [00:00:00.0009111 ago] @ ~13 () in 1 (Microsoft.DotNet.Interactive.App)\r\n         at System.Collections.Generic.StackPool`1.<>c.<New>b__9_0(ObjectPoolBase`1 p)\r\n         at System.Memory.PooledObject`1..ctor(ObjectPoolBase`1 pool, Func`2 allocator, Action`2 releaser)\r\n         at System.Collections.Generic.StackPool`1.New()\r\n         at <Notebook>\r\n      Free  - 21/03/04 16:58:39.7910145 [00:00:15.6958579 ago] @ ~4 () in 1 (Microsoft.DotNet.Interactive.App)\r\n         at System.Memory.ObjectPoolBase`1.Free(T obj)\r\n         at <Notebook>\r\n      Alloc - 21/03/04 16:58:39.7808835 [00:00:15.7065729 ago] @ ~4 () in 1 (Microsoft.DotNet.Interactive.App)\r\n         at System.Memory.ObjectPoolBase`1.Allocate()\r\n         at <Notebook>\r\n      \r\n\r\n\r\n\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "using (PooledStackHolder<int> h = pool.New())\n",
        "{\n",
        "    PrintDebugView();\n",
        "\n",
        "    var s = h.Stack;\n",
        "\n",
        "    // Use the object here.\n",
        "    s.Push(1);\n",
        "}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Now that we've returned the object back to the pool, let's inspect the pool again."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "System.Collections.Generic.StackPool`1+Impl0[System.Int32] : ObjectPoolBase<System.Collections.Generic.PooledStack`1[System.Int32]>\r\n===================================================================================================================================\r\n\r\nCreation trace\r\n--------------\r\n\r\n21/03/04 16:58:31.3985714 [00:00:28.0115706 ago] @ ~13 () in 1 (Microsoft.DotNet.Interactive.App)\r\n   at System.Memory.ObjectPoolBase`1..ctor(Int32 size)\r\n   at System.Collections.Generic.StackPool`1..ctor(Int32 size)\r\n   at System.Collections.Generic.StackPool`1.Impl0..ctor(Int32 size)\r\n   at System.Collections.Generic.StackPool`1.Create(Int32 size)\r\n   at <Notebook>\r\n\r\n\r\nStatistics\r\n----------\r\n\r\n  # slots:   8\r\n  # standby: 1\r\n  # allocs:  2\r\n  # frees:   2\r\n  # create:  1\r\n  # drops:   0\r\n\r\n  avg use time: 00:00:00.0078948\r\n  max use time: 00:00:00.0101310\r\n\r\n\r\nPool entries\r\n------------\r\n\r\n  [0] = #1\r\n  [1] = <empty>\r\n  [2] = <empty>\r\n  [3] = <empty>\r\n  [4] = <empty>\r\n  [5] = <empty>\r\n  [6] = <empty>\r\n  [7] = <empty>\r\n\r\n\r\nTracked objects\r\n---------------\r\n\r\n  #1 - standby\r\n  \r\n    Stats\r\n    ~~~~~\r\n\r\n      Usage count =  2\r\n      Max use time = 00:00:00.0101310\r\n      Avg use time = 00:00:00.0078948\r\n      \r\n    History\r\n    ~~~~~~~\r\n\r\n      Free  - 21/03/04 16:58:55.4909432 [00:00:03.9198422 ago] @ ~13 () in 1 (Microsoft.DotNet.Interactive.App)\r\n         at System.Collections.Generic.PooledStack`1.Free()\r\n         at System.Collections.Generic.StackPool`1.<>c.<New>b__9_1(ObjectPoolBase`1 _, PooledStack`1 o)\r\n         at System.Memory.PooledObject`1.Dispose()\r\n         at System.Collections.Generic.PooledStackHolder`1.Dispose()\r\n         at <Notebook>\r\n      Alloc - 21/03/04 16:58:55.4852846 [00:00:03.9259521 ago] @ ~13 () in 1 (Microsoft.DotNet.Interactive.App)\r\n         at System.Collections.Generic.StackPool`1.<>c.<New>b__9_0(ObjectPoolBase`1 p)\r\n         at System.Memory.PooledObject`1..ctor(ObjectPoolBase`1 pool, Func`2 allocator, Action`2 releaser)\r\n         at System.Collections.Generic.StackPool`1.New()\r\n         at <Notebook>\r\n      Free  - 21/03/04 16:58:39.7910145 [00:00:19.6206436 ago] @ ~4 () in 1 (Microsoft.DotNet.Interactive.App)\r\n         at System.Memory.ObjectPoolBase`1.Free(T obj)\r\n         at <Notebook>\r\n      Alloc - 21/03/04 16:58:39.7808835 [00:00:19.6311978 ago] @ ~4 () in 1 (Microsoft.DotNet.Interactive.App)\r\n         at System.Memory.ObjectPoolBase`1.Allocate()\r\n         at <Notebook>\r\n      \r\n\r\n\r\n\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "PrintDebugView();"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Use an object pool for a custom type\n",
        "\n",
        "To understand how object pools work at the next level of detail, let's use object pooling for a custom object type. There are a few ways to work with object pools, including deriving from `ObjectPoolBase<T>` or by using `ObjectPool<T>` directly. We'll explore the latter."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "#### Step 1 - Create a custom type\n",
        "\n",
        "To illustrate the behavior of pooling, we'll start by defining a custom type for which we'll pool instances."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "class MyObject\n",
        "{\n",
        "    // Demonstrates the expense of the object which may warrant pooling to reuse these array allocatons.\n",
        "    private readonly int[] _values = new int[16];\n",
        "\n",
        "    public int this[int i]\n",
        "    {\n",
        "        get => _values[i];\n",
        "        set => _values[i] = value;\n",
        "    }\n",
        "\n",
        "    public override string ToString() => string.Join(\", \", _values);\n",
        "}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "#### Step 2 - Create an object pool\n",
        "\n",
        "Next, rather than allocating `MyObject` instances directly, we'll use an `ObjectPool<MyObject>` which gets parameterized on a `Func<MyObject>` factory. For illustration purposes, we'll include a side-effect to indicate an allocation has taken place. The second `size` parameter passed to the constructor indicates the maximum number of instances held by the pool."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "using System.Memory;\n",
        "\n",
        "var myPool = new ObjectPool<MyObject>(() =>\n",
        "{\n",
        "    var res = new MyObject();\n",
        "    Console.WriteLine($\"Allocated a new MyObject instance. Hash code = {res.GetHashCode()}\");\n",
        "    return res;\n",
        "}, size: 4);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "#### Step 3 - Use the pool to allocate instances\n",
        "\n",
        "Let's now use our freshly created pool to allocate an instance of `MyObject` and witness the invocation of the factory."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "Allocated a new MyObject instance. Hash code = 12239935\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "42, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "MyObject myObj1 = myPool.Allocate();\n",
        "\n",
        "myObj1[0] = 42;\n",
        "\n",
        "Console.WriteLine(myObj1);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "#### Step 4 - Create a second object from the pool\n",
        "\n",
        "When we request another instance of `MyObject` from the pool while `myObj1` is in use, another allocation will take place. In this example, we use `New` which returns a `PooledObject<T>` which implements `IDisposable` to return the object to the pool. By using a `using` statement, the object gets returned to the pool automatically."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "Allocated a new MyObject instance. Hash code = 31965818\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "43, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "using (PooledObject<MyObject> myObj2 = myPool.New())\n",
        "{\n",
        "    myObj2.Object[0] = 43;\n",
        "\n",
        "    Console.WriteLine(myObj2.Object);\n",
        "}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "#### Step 5 - Witness the reuse of objects\n",
        "\n",
        "To illustrate the reuse of objects from the pool, let's allocate yet another object from the pool. Because we still are holding on to `myObj1` but have used and released `myObj2`, the latter object can be reused. Note that the hash code of the object returned from the pool matches `myObj2` in the cell above."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "Hash code = 31965818\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "43, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "using (PooledObject<MyObject> myObj3 = myPool.New())\n",
        "{\n",
        "    Console.WriteLine($\"Hash code = {myObj3.Object.GetHashCode()}\");\n",
        "\n",
        "    Console.WriteLine(myObj3.Object);\n",
        "}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Note that the instance that was returned still has the mutated state in the array from the last time the object was used. This may pose a security issue in some cases where it may be warranted to clear the contents of an object prior to returning it to the pool. To support this, we can implement additional interfaces on the pooled object type. We'll get to this in a moment."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "#### Step 6 - Exploring pooling behavior a bit more\n",
        "\n",
        "What happens if we allocate more objects than the specified `size` of the object pool? To figure this out, let's allocate a bunch more objects from the pool. But first, let's return `myObj1` to the pool."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "myPool.Free(myObj1);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "It goes without saying that `myObj1` should no longer be used after it has been returned to the pool because it can be used by some other piece of code at any time after having been returned. The use of `New` with a `using` statement makes it a bit harder to have this type of *use-after-free* bugs, but one should remain cautious and carefully review usage patterns of pooled objects.\n",
        "\n",
        "Now, let's allocate more objects than fit in our pool. The pool's size is `4`, so let's allocate `5` objects."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "objs[0].GetHashCode() = 31965818\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "objs[1].GetHashCode() = 12239935\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "Allocated a new MyObject instance. Hash code = 45407009\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "objs[2].GetHashCode() = 45407009\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "Allocated a new MyObject instance. Hash code = 46471022\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "objs[3].GetHashCode() = 46471022\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "Allocated a new MyObject instance. Hash code = 46242629\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "objs[4].GetHashCode() = 46242629\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var objs = new MyObject[5];\n",
        "\n",
        "for (var i = 0; i < objs.Length; i++)\n",
        "{\n",
        "    objs[i] = myPool.Allocate();\n",
        "\n",
        "    Console.WriteLine($\"objs[{i}].GetHashCode() = {objs[i].GetHashCode()}\");\n",
        "}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Note that the first two objects are reused from the `myObj1` and `myObj2` allocations we did earlier. The remainder three objects were freshly allocated. Now, we'll return all of them back to the pool."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "for (var i = 0; i < objs.Length; i++)\n",
        "{\n",
        "    myPool.Free(objs[i]);\n",
        "}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "If we allocate another `5` objects now, we'll get four that get reused from the pool (because of its maximum size of `4`), while the fifth one will be new."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "objs[0].GetHashCode() = 31965818\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "objs[1].GetHashCode() = 12239935\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "objs[2].GetHashCode() = 45407009\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "objs[3].GetHashCode() = 46471022\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "Allocated a new MyObject instance. Hash code = 45672827\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "objs[4].GetHashCode() = 45672827\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var objs = new MyObject[5];\n",
        "\n",
        "for (var i = 0; i < objs.Length; i++)\n",
        "{\n",
        "    objs[i] = myPool.Allocate();\n",
        "\n",
        "    Console.WriteLine($\"objs[{i}].GetHashCode() = {objs[i].GetHashCode()}\");\n",
        "}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "#### Step 7 - Support clearing an instance upon returning to the pool\n",
        "\n",
        "To support clearing an instance prior to returning it to the pool, we can implement the `IClearable` interface on `MyObject`."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "class MyObject : IClearable\n",
        "{\n",
        "    // Demonstrates the expense of the object which may warrant pooling to reuse these array allocatons.\n",
        "    private readonly int[] _values = new int[16];\n",
        "\n",
        "    public int this[int i]\n",
        "    {\n",
        "        get => _values[i];\n",
        "        set => _values[i] = value;\n",
        "    }\n",
        "\n",
        "    public void Clear() => Array.Clear(_values, 0, _values.Length);\n",
        "\n",
        "    public override string ToString() => string.Join(\", \", _values);\n",
        "}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Let's create a new pool, just like we did before. We'll keep the side-effect in the factory delegate to spot reuse of objects further on."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "using System.Memory;\n",
        "\n",
        "var myPool = new ObjectPool<MyObject>(() =>\n",
        "{\n",
        "    var res = new MyObject();\n",
        "    Console.WriteLine($\"Allocated a new MyObject instance. Hash code = {res.GetHashCode()}\");\n",
        "    return res;\n",
        "}, size: 4);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Finally, let's allocate an object, mutate it, return it to the pool, and then allocate another object. This will cause reuse of the object. However, this time around we should not see the result of mutating the array upon reusing the same instance, because `IClearable.Clear` has been called by the pool."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "First usage of the object\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "Allocated a new MyObject instance. Hash code = 39493100\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "obj#39493100 = 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "obj#39493100 = 42, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "Second usage of the object\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "obj#39493100 = 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "obj#39493100 = 42, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "Console.WriteLine(\"First usage of the object\");\n",
        "\n",
        "using (var obj = myPool.New())\n",
        "{\n",
        "    Console.WriteLine($\"obj#{obj.Object.GetHashCode()} = {obj.Object}\");\n",
        "    obj.Object[0] = 42;\n",
        "    Console.WriteLine($\"obj#{obj.Object.GetHashCode()} = {obj.Object}\");\n",
        "}\n",
        "\n",
        "Console.WriteLine(\"Second usage of the object\");\n",
        "\n",
        "using (var obj = myPool.New())\n",
        "{\n",
        "    Console.WriteLine($\"obj#{obj.Object.GetHashCode()} = {obj.Object}\"); // Contents should be clear!\n",
        "    obj.Object[0] = 42;\n",
        "    Console.WriteLine($\"obj#{obj.Object.GetHashCode()} = {obj.Object}\");\n",
        "}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Function memoization\n",
        "\n",
        "Function memoization is a technique to cache the results of evaluating a pure function in order to speed up future invocations."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### A trivial example using the Fibonacci sequence\n",
        "\n",
        "As an example, consider the well-known recursive Fibonacci generator."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "Func<long, long> fib = null;\n",
        "\n",
        "fib = n => n <= 1 ? 1 : checked(fib(n - 1) + fib(n - 2));"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Evaluating the Fibonacci generator causes repeated evaluation of the same function with the same argument. For example:\n",
        "\n",
        "```\n",
        "fib(3) = fib(2) + fib(1)\n",
        "fib(2) =          fib(1) + fib(0)\n",
        "```\n",
        "\n",
        "Let's run the Fibonacci generator for a few values and time the execution."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "fib(0) = 1 - Took 00:00:00.0000998\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(1) = 1 - Took 00:00:00.0000002\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(2) = 2 - Took 00:00:00.0000001\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(3) = 3 - Took 00:00:00.0000004\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(4) = 5 - Took 00:00:00.0000001\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(5) = 8 - Took 00:00:00.0000002\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(6) = 13 - Took 00:00:00.0000002\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(7) = 21 - Took 00:00:00.0000002\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(8) = 34 - Took 00:00:00.0000003\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(9) = 55 - Took 00:00:00.0000005\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(10) = 89 - Took 00:00:00.0000008\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(11) = 144 - Took 00:00:00.0000012\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(12) = 233 - Took 00:00:00.0000019\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(13) = 377 - Took 00:00:00.0000030\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(14) = 610 - Took 00:00:00.0000048\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(15) = 987 - Took 00:00:00.0000076\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(16) = 1597 - Took 00:00:00.0000123\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(17) = 2584 - Took 00:00:00.0000200\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(18) = 4181 - Took 00:00:00.0000323\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(19) = 6765 - Took 00:00:00.0000521\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(20) = 10946 - Took 00:00:00.0000843\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(21) = 17711 - Took 00:00:00.0001366\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(22) = 28657 - Took 00:00:00.0002287\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(23) = 46368 - Took 00:00:00.0003679\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(24) = 75025 - Took 00:00:00.0005690\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(25) = 121393 - Took 00:00:00.0009238\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(26) = 196418 - Took 00:00:00.0015070\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(27) = 317811 - Took 00:00:00.0023645\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(28) = 514229 - Took 00:00:00.0037919\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(29) = 832040 - Took 00:00:00.0066606\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(30) = 1346269 - Took 00:00:00.0184343\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(31) = 2178309 - Took 00:00:00.0170979\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(32) = 3524578 - Took 00:00:00.0252016\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(33) = 5702887 - Took 00:00:00.0422791\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(34) = 9227465 - Took 00:00:00.0661603\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(35) = 14930352 - Took 00:00:00.1092889\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(36) = 24157817 - Took 00:00:00.1707919\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(37) = 39088169 - Took 00:00:00.2902803\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(38) = 63245986 - Took 00:00:00.4512719\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(39) = 102334155 - Took 00:00:00.7811258\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(40) = 165580141 - Took 00:00:01.3919132\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(41) = 267914296 - Took 00:00:02.1608034\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(42) = 433494437 - Took 00:00:03.1233396\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(43) = 701408733 - Took 00:00:05.2934294\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "Aborted at iteration 43. This is starting to take too long.\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "using System.Diagnostics;\n",
        "\n",
        "void PrintFibonacci(int max, TimeSpan maxTimeToCompute)\n",
        "{\n",
        "    var sw = new Stopwatch();\n",
        "\n",
        "    for (int i = 0; i < max; i++)\n",
        "    {\n",
        "        sw.Restart();\n",
        "\n",
        "        long res = 0L;\n",
        "        try\n",
        "        {\n",
        "            res = fib(i);\n",
        "        }\n",
        "        catch (OverflowException)\n",
        "        {\n",
        "            Console.WriteLine($\"fib({i}) = Overflow\");\n",
        "            return;\n",
        "        }\n",
        "\n",
        "        sw.Stop();\n",
        "        Console.WriteLine($\"fib({i}) = {res} - Took {sw.Elapsed}\");\n",
        "\n",
        "        // Stop if it starts taking too long.\n",
        "        if (sw.Elapsed > maxTimeToCompute)\n",
        "        {\n",
        "            Console.WriteLine($\"Aborted at iteration {i}. This is starting to take too long.\");\n",
        "            break;\n",
        "        }\n",
        "    }\n",
        "}\n",
        "\n",
        "PrintFibonacci(100, TimeSpan.FromSeconds(5));"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Most likely, you didn't get much further than some `40`-ish iterations. Let's use this example to illustrate memoization for function evaluation."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "The first step to make memoization work is to create a so-called *memoization cache factory*. Each memoized function will have an associated memoization cache. Factories for such caches determine the policy of the cache. In the sample below we'll use an `Unbounded` cache which does not limit the number of entries in the cache. Other options are caches with least-recently-used (LRU) policies or other eviction policies."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "using System.Memory;\n",
        "\n",
        "IMemoizationCacheFactory factory = MemoizationCacheFactory.Unbounded;"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Now that we have a cache factory, we can create a *memoizer* that will be used to memoize functions."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "IMemoizer mem = Memoizer.Create(factory);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Finally, we use the memoizer to `Memoize` the function. After doing so, we end up with a pair of a cache and a memoized function of the same delegate type."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "fib(0) = 1 - Took 00:00:00.0036124\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(1) = 1 - Took 00:00:00.0000302\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(2) = 2 - Took 00:00:00.0001916\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(3) = 3 - Took 00:00:00.0006244\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(4) = 5 - Took 00:00:00.0000033\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(5) = 8 - Took 00:00:00.0000008\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(6) = 13 - Took 00:00:00.0000004\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(7) = 21 - Took 00:00:00.0000011\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(8) = 34 - Took 00:00:00.0000004\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(9) = 55 - Took 00:00:00.0000004\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(10) = 89 - Took 00:00:00.0000004\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(11) = 144 - Took 00:00:00.0000004\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(12) = 233 - Took 00:00:00.0000003\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(13) = 377 - Took 00:00:00.0000003\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(14) = 610 - Took 00:00:00.0000004\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(15) = 987 - Took 00:00:00.0000003\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(16) = 1597 - Took 00:00:00.0000005\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(17) = 2584 - Took 00:00:00.0000008\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(18) = 4181 - Took 00:00:00.0000005\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(19) = 6765 - Took 00:00:00.0000009\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(20) = 10946 - Took 00:00:00.0000004\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(21) = 17711 - Took 00:00:00.0000018\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(22) = 28657 - Took 00:00:00.0000005\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(23) = 46368 - Took 00:00:00.0000004\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(24) = 75025 - Took 00:00:00.0000004\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(25) = 121393 - Took 00:00:00.0000003\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(26) = 196418 - Took 00:00:00.0000004\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(27) = 317811 - Took 00:00:00.0000004\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(28) = 514229 - Took 00:00:00.0000003\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(29) = 832040 - Took 00:00:00.0000003\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(30) = 1346269 - Took 00:00:00.0000004\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(31) = 2178309 - Took 00:00:00.0000004\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(32) = 3524578 - Took 00:00:00.0000003\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(33) = 5702887 - Took 00:00:00.0000005\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(34) = 9227465 - Took 00:00:00.0000003\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(35) = 14930352 - Took 00:00:00.0000003\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(36) = 24157817 - Took 00:00:00.0000004\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(37) = 39088169 - Took 00:00:00.0000029\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(38) = 63245986 - Took 00:00:00.0000004\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(39) = 102334155 - Took 00:00:00.0000003\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(40) = 165580141 - Took 00:00:00.0000004\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(41) = 267914296 - Took 00:00:00.0000004\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(42) = 433494437 - Took 00:00:00.0000004\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(43) = 701408733 - Took 00:00:00.0000003\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(44) = 1134903170 - Took 00:00:00.0000003\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(45) = 1836311903 - Took 00:00:00.0000004\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(46) = 2971215073 - Took 00:00:00.0000003\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(47) = 4807526976 - Took 00:00:00.0000004\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(48) = 7778742049 - Took 00:00:00.0000004\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(49) = 12586269025 - Took 00:00:00.0000004\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(50) = 20365011074 - Took 00:00:00.0000008\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(51) = 32951280099 - Took 00:00:00.0000003\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(52) = 53316291173 - Took 00:00:00.0000004\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(53) = 86267571272 - Took 00:00:00.0000003\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(54) = 139583862445 - Took 00:00:00.0000004\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(55) = 225851433717 - Took 00:00:00.0000004\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(56) = 365435296162 - Took 00:00:00.0000003\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(57) = 591286729879 - Took 00:00:00.0000003\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(58) = 956722026041 - Took 00:00:00.0000004\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(59) = 1548008755920 - Took 00:00:00.0000004\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(60) = 2504730781961 - Took 00:00:00.0000004\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(61) = 4052739537881 - Took 00:00:00.0000003\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(62) = 6557470319842 - Took 00:00:00.0000003\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(63) = 10610209857723 - Took 00:00:00.0000004\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(64) = 17167680177565 - Took 00:00:00.0000003\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(65) = 27777890035288 - Took 00:00:00.0000004\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(66) = 44945570212853 - Took 00:00:00.0000004\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(67) = 72723460248141 - Took 00:00:00.0000003\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(68) = 117669030460994 - Took 00:00:00.0000003\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(69) = 190392490709135 - Took 00:00:00.0000003\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(70) = 308061521170129 - Took 00:00:00.0000006\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(71) = 498454011879264 - Took 00:00:00.0000003\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(72) = 806515533049393 - Took 00:00:00.0000003\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(73) = 1304969544928657 - Took 00:00:00.0000004\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(74) = 2111485077978050 - Took 00:00:00.0000004\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(75) = 3416454622906707 - Took 00:00:00.0000010\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(76) = 5527939700884757 - Took 00:00:00.0000003\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(77) = 8944394323791464 - Took 00:00:00.0000004\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(78) = 14472334024676221 - Took 00:00:00.0000004\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(79) = 23416728348467685 - Took 00:00:00.0000003\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(80) = 37889062373143906 - Took 00:00:00.0000005\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(81) = 61305790721611591 - Took 00:00:00.0000004\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(82) = 99194853094755497 - Took 00:00:00.0000003\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(83) = 160500643816367088 - Took 00:00:00.0000003\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(84) = 259695496911122585 - Took 00:00:00.0000003\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(85) = 420196140727489673 - Took 00:00:00.0000003\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(86) = 679891637638612258 - Took 00:00:00.0000003\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(87) = 1100087778366101931 - Took 00:00:00.0000003\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(88) = 1779979416004714189 - Took 00:00:00.0000003\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(89) = 2880067194370816120 - Took 00:00:00.0000088\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(90) = 4660046610375530309 - Took 00:00:00.0000004\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(91) = 7540113804746346429 - Took 00:00:00.0000004\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "fib(92) = Overflow\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "IMemoizedDelegate<Func<long, long>> memoizedDelegateFib = mem.Memoize(fib);\n",
        "\n",
        "// The cache and delegate pair.\n",
        "IMemoizationCache cache = memoizedDelegateFib.Cache;\n",
        "Func<long, long> fibMemoized = memoizedDelegateFib.Delegate;\n",
        "\n",
        "// Let's replace the original delegate by the memoized one, which was also used in the body of the recursive definition of fib.\n",
        "fib = fibMemoized;\n",
        "\n",
        "// Now we should get much further along.\n",
        "PrintFibonacci(100, TimeSpan.FromSeconds(5));"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "To see what's going on, let's explore the cache."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "Number of entries = 92\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "cache.DebugView"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "While the output of `DebugView` is a bit spartan, note that we have `92` entries which contain the values of evaluating `fib(0)` through `fib(91)`. We can also go ahead and clear the cache manually, using the `Clear` method.\n",
        "\n",
        "**Note:** The use of `Clear` is atypical but is sometimes useful after performing a lot of operations in a certain \"phase\" of execution in a program and where it makes sense to reclaim resources. Caches in Nuqleon are not actively maintained; there are no background threads or timers to prune caches when they're not in use. However, simply dropping the reference to the memoized delegate will also cause the cache to get garbage collected. That's often a more convenient approach to manage caches."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "Number of entries = 0\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "cache.Clear();\n",
        "\n",
        "cache.DebugView"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Exploring memoization in more detail\n",
        "\n",
        "To explore what's going on, let's craft a more sophisticated example using an instrumented function."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "using System.Threading;\n",
        "\n",
        "static double GetRadius(double x, double y)\n",
        "{\n",
        "    Console.WriteLine($\"GetRadius({x}, {y}) was called\");\n",
        "    Thread.Sleep(1000);\n",
        "    return Math.Sqrt(x * x + y * y);\n",
        "}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Invoking this function directly takes a little over a second to complete, mimicking the expense of a real function."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "GetRadius(3, 4) was called\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "GetRadius(3, 4) = 5 in 00:00:01.0052418\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var sw = Stopwatch.StartNew();\n",
        "Console.WriteLine($\"GetRadius(3, 4) = {GetRadius(3, 4)} in {sw.Elapsed}\");"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "By using memoization, we can cache and reuse the result. This time around, we'll create an LRU cache to explore cache policies."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "using System.Memory;\n",
        "\n",
        "IMemoizationCacheFactory factory = MemoizationCacheFactory.CreateLru(maxCapacity: 4);\n",
        "\n",
        "IMemoizer memoizer = Memoizer.Create(factory);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Unlike our Fibonacci example, we start off with a method here, rather than a delegate. Furthermore, we have more than one parameter in this case. To pick the right overload of `Memoize`, we will be explicit about the parameter and result types. As a result, we'll end up with a `Func<double, double, double>` delegate that represents the memoized `GetRadius` method. While we're at it, we'll also explore other parameters of `Memoize`, all of which are optional and have suitable defaults."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "IMemoizedDelegate<Func<double, double, double>> getRadiusMemoized = memoizer.Memoize<double, double, double>(GetRadius, MemoizationOptions.CacheException, EqualityComparer<double>.Default, EqualityComparer<double>.Default);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "The first additional parameter is a `MemoizationOptions` enum which enables turning on caching of exceptions in case the function throws. This is off by default. In our example, this is obviously quite useless. The additional two parameters are `IEqualityComparer<T>` instances for the two inputs of the `GetRadius` function. These are used to look up existing `x, y` pairs in the cache when trying to find a match. An example where this can be useful is for functions that take in an array and one wants to check the array for element-wise equality.\n",
        "\n",
        "**Note:** A concrete example of memoization is in `Nuqleon.Reflection.Virtualization` where expensive reflection calls get memoized. This touches on various design points mentioned here. For example, some APIs may throw an exception, and we may want to cache these. Also, APIs like `MakeGenericType` take in a `Type[]` and memoization requires a way to compare two such arrays for element-wise equality.\n",
        "\n",
        "With the resulting memoized delegate, we can now see the behavior of repeated invocation of `GetRadius` with memoization applied."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "GetRadius(3, 4) was called\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "GetRadius(3, 4) = 5 in 00:00:01.0102280\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "GetRadius(3, 4) = 5 in 00:00:00.0003059\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var sw = Stopwatch.StartNew();\n",
        "Console.WriteLine($\"GetRadius(3, 4) = {getRadiusMemoized.Delegate(3, 4)} in {sw.Elapsed}\");\n",
        "\n",
        "sw.Restart();\n",
        "Console.WriteLine($\"GetRadius(3, 4) = {getRadiusMemoized.Delegate(3, 4)} in {sw.Elapsed}\");"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Note that the second invocation did not trigger the invocation of `GetRadius` and served up the result from the cache. Let's now print the cache's `DebugView`, clear the cache, and try to invoke the memoized delegate again."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "Entries\r\n-------\r\n\r\n  (3, 4) -> 5\r\n    Invoke duration     = 00:00:01.0013880\r\n    Hit count           = 2\r\n    Average access time = 00:00:00.5047844\r\n    Speed up factor     = 1.9837934769774976\r\n\r\nSummary\r\n-------\r\n\r\n  Invocation count = 1\r\n  Access count     = 2\r\n  Eviction count   = 0\r\n\r\n\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "GetRadius(3, 4) was called\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "GetRadius(3, 4) = 5 in 00:00:01.0153758\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "GetRadius(3, 4) = 5 in 00:00:00.0000438\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "Console.WriteLine(getRadiusMemoized.Cache.DebugView);\n",
        "\n",
        "getRadiusMemoized.Cache.Clear();\n",
        "\n",
        "sw.Restart();\n",
        "Console.WriteLine($\"GetRadius(3, 4) = {getRadiusMemoized.Delegate(3, 4)} in {sw.Elapsed}\");\n",
        "\n",
        "sw.Restart();\n",
        "Console.WriteLine($\"GetRadius(3, 4) = {getRadiusMemoized.Delegate(3, 4)} in {sw.Elapsed}\");"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Note that the `DebugView` output is much more verbose. This is because we're now using an LRU cache which has a much more elaborate `DebugView` to analyze what's going on. For our initial exploration, keep an eye on `Eviction count`, which will reflect the LRU behavior where the least recently used entry gets evicted from the cache. To illustrate this, let's invoke the memoized delegate with various inputs."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "GetRadius(1, 2) was called\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "GetRadius(1, 2) = 2.23606797749979 in 00:00:01.0120257\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "GetRadius(2, 3) was called\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "GetRadius(2, 3) = 3.605551275463989 in 00:00:01.0046993\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "GetRadius(3, 4) = 5 in 00:00:00.0000081\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "GetRadius(1, 2) = 2.23606797749979 in 00:00:00.0000033\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "GetRadius(2, 3) = 3.605551275463989 in 00:00:00.0000029\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "GetRadius(3, 4) = 5 in 00:00:00.0000023\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "Entries\r\n-------\r\n\r\n  (3, 4) -> 5\r\n    Invoke duration     = 00:00:01.0152318\r\n    Hit count           = 4\r\n    Average access time = 00:00:00.2538540\r\n    Speed up factor     = 3.999274386064431\r\n\r\n  (2, 3) -> 3.605551275463989\r\n    Invoke duration     = 00:00:01.0046303\r\n    Hit count           = 2\r\n    Average access time = 00:00:00.5023476\r\n    Speed up factor     = 1.9998708065889037\r\n\r\n  (1, 2) -> 2.23606797749979\r\n    Invoke duration     = 00:00:01.0119472\r\n    Hit count           = 2\r\n    Average access time = 00:00:00.5060107\r\n    Speed up factor     = 1.999853362784621\r\n\r\nSummary\r\n-------\r\n\r\n  Invocation count = 3\r\n  Access count     = 8\r\n  Eviction count   = 0\r\n\r\n\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "for (int i = 0; i < 2; i++)\n",
        "{\n",
        "    foreach (var (x, y) in new[] {\n",
        "        (1, 2),\n",
        "        (2, 3),\n",
        "        (3, 4),\n",
        "    })\n",
        "    {\n",
        "        sw.Restart();\n",
        "        Console.WriteLine($\"GetRadius({x}, {y}) = {getRadiusMemoized.Delegate(x, y)} in {sw.Elapsed}\");\n",
        "    }\n",
        "}\n",
        "\n",
        "Console.WriteLine(getRadiusMemoized.Cache.DebugView);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Because we've only invoked the function with three distinct input pairs, we never ended up causing any eviction. The order of the entries in the `DebugView` shows the latest invocation at the top. Let's make another invocation for a unique input."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "GetRadius(4, 5) was called\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "GetRadius(4, 5) = 6.4031242374328485 in 00:00:01.0039645\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "Entries\r\n-------\r\n\r\n  (4, 5) -> 6.4031242374328485\r\n    Invoke duration     = 00:00:01.0026460\r\n    Hit count           = 1\r\n    Average access time = 00:00:01.0039598\r\n    Speed up factor     = 0.9986913818660866 [DEGRADATION]\r\n\r\n  (3, 4) -> 5\r\n    Invoke duration     = 00:00:01.0152318\r\n    Hit count           = 4\r\n    Average access time = 00:00:00.2538540\r\n    Speed up factor     = 3.999274386064431\r\n\r\n  (2, 3) -> 3.605551275463989\r\n    Invoke duration     = 00:00:01.0046303\r\n    Hit count           = 2\r\n    Average access time = 00:00:00.5023476\r\n    Speed up factor     = 1.9998708065889037\r\n\r\n  (1, 2) -> 2.23606797749979\r\n    Invoke duration     = 00:00:01.0119472\r\n    Hit count           = 2\r\n    Average access time = 00:00:00.5060107\r\n    Speed up factor     = 1.999853362784621\r\n\r\nSummary\r\n-------\r\n\r\n  Invocation count = 4\r\n  Access count     = 9\r\n  Eviction count   = 0\r\n\r\n\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "sw.Restart();\n",
        "Console.WriteLine($\"GetRadius(4, 5) = {getRadiusMemoized.Delegate(4, 5)} in {sw.Elapsed}\");\n",
        "\n",
        "Console.WriteLine(getRadiusMemoized.Cache.DebugView);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Now, the cache is full. To see the order of the entries change, we can make some more invocations with these input pairs. All accesses will be sped up because they get served from the cache."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "GetRadius(4, 5) = 6.4031242374328485 in 00:00:00.0000144\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "GetRadius(1, 2) = 2.23606797749979 in 00:00:00.0000095\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "GetRadius(2, 3) = 3.605551275463989 in 00:00:00.0000017\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "GetRadius(3, 4) = 5 in 00:00:00.0000030\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "Entries\r\n-------\r\n\r\n  (3, 4) -> 5\r\n    Invoke duration     = 00:00:01.0152318\r\n    Hit count           = 5\r\n    Average access time = 00:00:00.2030838\r\n    Speed up factor     = 4.999078213033241\r\n\r\n  (2, 3) -> 3.605551275463989\r\n    Invoke duration     = 00:00:01.0046303\r\n    Hit count           = 3\r\n    Average access time = 00:00:00.3348989\r\n    Speed up factor     = 2.9998017312090304\r\n\r\n  (1, 2) -> 2.23606797749979\r\n    Invoke duration     = 00:00:01.0119472\r\n    Hit count           = 3\r\n    Average access time = 00:00:00.3373434\r\n    Speed up factor     = 2.999753959911473\r\n\r\n  (4, 5) -> 6.4031242374328485\r\n    Invoke duration     = 00:00:01.0026460\r\n    Hit count           = 2\r\n    Average access time = 00:00:00.5019845\r\n    Speed up factor     = 1.9973644604564484\r\n\r\nSummary\r\n-------\r\n\r\n  Invocation count = 4\r\n  Access count     = 13\r\n  Eviction count   = 0\r\n\r\n\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "foreach (var (x, y) in new[] {\n",
        "    (4, 5),\n",
        "    (1, 2),\n",
        "    (2, 3),\n",
        "    (3, 4),\n",
        "})\n",
        "{\n",
        "    sw.Restart();\n",
        "    Console.WriteLine($\"GetRadius({x}, {y}) = {getRadiusMemoized.Delegate(x, y)} in {sw.Elapsed}\");\n",
        "}\n",
        "\n",
        "Console.WriteLine(getRadiusMemoized.Cache.DebugView);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Now, the input pair `(4, 5)` is the least recently used one. Let's try to invoke the memoized function with a new unique input pair, and see this entry getting evicted."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "GetRadius(5, 6) was called\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "GetRadius(5, 6) = 7.810249675906654 in 00:00:01.0163047\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "Entries\r\n-------\r\n\r\n  (5, 6) -> 7.810249675906654\r\n    Invoke duration     = 00:00:01.0150146\r\n    Hit count           = 1\r\n    Average access time = 00:00:01.0162988\r\n    Speed up factor     = 0.998736395241242 [DEGRADATION]\r\n\r\n  (3, 4) -> 5\r\n    Invoke duration     = 00:00:01.0152318\r\n    Hit count           = 5\r\n    Average access time = 00:00:00.2030838\r\n    Speed up factor     = 4.999078213033241\r\n\r\n  (2, 3) -> 3.605551275463989\r\n    Invoke duration     = 00:00:01.0046303\r\n    Hit count           = 3\r\n    Average access time = 00:00:00.3348989\r\n    Speed up factor     = 2.9998017312090304\r\n\r\n  (1, 2) -> 2.23606797749979\r\n    Invoke duration     = 00:00:01.0119472\r\n    Hit count           = 3\r\n    Average access time = 00:00:00.3373434\r\n    Speed up factor     = 2.999753959911473\r\n\r\nSummary\r\n-------\r\n\r\n  Invocation count = 5\r\n  Access count     = 14\r\n  Eviction count   = 1\r\n\r\n  Last eviction\r\n    Invoke duration     = 00:00:01.0026460\r\n    Hit count           = 2\r\n    Average access time = 00:00:00.5019845\r\n    Speed up factor     = 1.9973644604564484\r\n\r\n\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "sw.Restart();\n",
        "Console.WriteLine($\"GetRadius(5, 6) = {getRadiusMemoized.Delegate(5, 6)} in {sw.Elapsed}\");\n",
        "\n",
        "Console.WriteLine(getRadiusMemoized.Cache.DebugView);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "The eviction count is `1` now. If we try to invoke the delegate with inputs `(4, 5)` again, we'll see `GetRadius` getting invoked again. This time, `(1, 2)` is the least recently used entry which will get evicted."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "GetRadius(4, 5) was called\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "GetRadius(4, 5) = 6.4031242374328485 in 00:00:01.0060432\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "Entries\r\n-------\r\n\r\n  (4, 5) -> 6.4031242374328485\r\n    Invoke duration     = 00:00:01.0059979\r\n    Hit count           = 1\r\n    Average access time = 00:00:01.0060376\r\n    Speed up factor     = 0.9999605382542363 [DEGRADATION]\r\n\r\n  (5, 6) -> 7.810249675906654\r\n    Invoke duration     = 00:00:01.0150146\r\n    Hit count           = 1\r\n    Average access time = 00:00:01.0162988\r\n    Speed up factor     = 0.998736395241242 [DEGRADATION]\r\n\r\n  (3, 4) -> 5\r\n    Invoke duration     = 00:00:01.0152318\r\n    Hit count           = 5\r\n    Average access time = 00:00:00.2030838\r\n    Speed up factor     = 4.999078213033241\r\n\r\n  (2, 3) -> 3.605551275463989\r\n    Invoke duration     = 00:00:01.0046303\r\n    Hit count           = 3\r\n    Average access time = 00:00:00.3348989\r\n    Speed up factor     = 2.9998017312090304\r\n\r\nSummary\r\n-------\r\n\r\n  Invocation count = 6\r\n  Access count     = 15\r\n  Eviction count   = 2\r\n\r\n  Last eviction\r\n    Invoke duration     = 00:00:01.0119472\r\n    Hit count           = 3\r\n    Average access time = 00:00:00.3373434\r\n    Speed up factor     = 2.999753959911473\r\n\r\n\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "sw.Restart();\n",
        "Console.WriteLine($\"GetRadius(4, 5) = {getRadiusMemoized.Delegate(4, 5)} in {sw.Elapsed}\");\n",
        "\n",
        "Console.WriteLine(getRadiusMemoized.Cache.DebugView);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### More advanced cache policies\n",
        "\n",
        "In the samples above we've seen the use of an unbounded and an LRU-based cache for memoization. The `Nuqleon.Memory` library also supports more advanced cache management schemes.\n",
        "\n",
        "A first example is the use of `CreateEvictedBy[Highest|Lowest]` for any metric on `IMemoizationCacheEntryMetrics`. In fact, the LRU policy is merely performing an eviction based on the `LastAccessTime` metric that's kept for entries in the cache. In the sample below, we'll use the `SpeedUpFactory` metric which represents a ratio between the time it took to invoke the function for the given arguments, prior to caching the result, and the time taken by subsequent invocations, served from the cache."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "static int GetValueDelayed(int x, int ms)\n",
        "{\n",
        "    Thread.Sleep(ms);\n",
        "    return x;\n",
        "}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "The `GetValueDelayed` function illustrates the difference in time needed to invoke a function based on its arguments. We can now memoize the function using `CreateEvictedByLowest` using the `SpeedupFactory` metric. We'll also limit the cache to 4 entries using the `maxCapacity` parameter.\n",
        "\n",
        "**Note:** The `ageThreshold` parameter is slightly more complex. Every time the memoization cache gets accessed, the cache entry that was used to satisfy the request (i.e. either an existing entry or a freshly created one) is moved to the top of an internal data structure. This keeps them ordered by the last access time, which is directly usable for LRU policies. When an eviction has to be made based on another metric, the tail of this list of entries is used to find a candidate, excluding the most recent items. This is done to give recent items a chance to get more statistically relevant data, especially for new entries that shouldn't get evicted immediately. The `ageThreshold` specifies this cut-off point. By setting it to `1.0` rather than the default of `0.9`, we will consider all cache entries valid to be valid as eviction candidates."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "var factory = MemoizationCacheFactory.CreateEvictedByLowest(metric => metric.SpeedupFactor, maxCapacity: 4, ageThreshold: 1.0);\n",
        "\n",
        "var memoizer = Memoizer.Create(factory);\n",
        "\n",
        "var getValueDelayedMemoized = memoizer.Memoize<int, int, int>(GetValueDelayed);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Also note that the delegate passed to `CreateEvictedByLowest` can contain any computation based on the given metrics, so users are free to compute other derived metrics in case the built-in ones do not meet certain criteria. Using this delegate it's also possible to create a random eviction policy, simply by returning a random number.\n",
        "\n",
        "Now we'll go ahead and invoke the memoized function for a few times different inputs which will cause the computation of metrics for each entry, as shown by dumping the cache's `DebugView`."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "Entries\r\n-------\r\n\r\n  (42, 10) -> 42\r\n    Invoke duration     = 00:00:00.0223207\r\n    Hit count           = 100\r\n    Average access time = 00:00:00.0002765\r\n    Speed up factor     = 80.72585895117541\r\n\r\n  (42, 20) -> 42\r\n    Invoke duration     = 00:00:00.0283414\r\n    Hit count           = 100\r\n    Average access time = 00:00:00.0002853\r\n    Speed up factor     = 99.33894146512444\r\n\r\n  (42, 30) -> 42\r\n    Invoke duration     = 00:00:00.0315064\r\n    Hit count           = 100\r\n    Average access time = 00:00:00.0003152\r\n    Speed up factor     = 99.95685279187818\r\n\r\n  (42, 40) -> 42\r\n    Invoke duration     = 00:00:00.0480687\r\n    Hit count           = 100\r\n    Average access time = 00:00:00.0004882\r\n    Speed up factor     = 98.46108152396559\r\n\r\nSummary\r\n-------\r\n\r\n  Invocation count = 4\r\n  Access count     = 400\r\n  Trim count       = 0\r\n  Trim elapsed     = 00:00:00\r\n  Eviction count   = 0\r\n\r\n\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "for (int i = 0; i < 100; i++)\n",
        "{\n",
        "    for (int j = 1; j <= 4; j++)\n",
        "    {\n",
        "        getValueDelayedMemoized.Delegate(42, j * 10);\n",
        "    }\n",
        "}\n",
        "\n",
        "Console.WriteLine(getValueDelayedMemoized.Cache.DebugView);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "The reported speed up factor for the different entries will differ slightly after the decimal point, where the 40ms invocation of the function has the highest speed up and the 10ms invocation of the function has the lowest speed up. Upon doing a new invocation that requires the eviction of an entry, the entry with the lowest speed up will be evicted. In the cell below, we invoke the function with a different argument value to cause eviction."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "Entries\r\n-------\r\n\r\n  (43, 10) -> 43\r\n    Invoke duration     = 00:00:00.0243194\r\n    Hit count           = 1\r\n    Average access time = 00:00:00.0279688\r\n    Speed up factor     = 0.8695188924801922 [DEGRADATION]\r\n\r\n  (42, 20) -> 42\r\n    Invoke duration     = 00:00:00.0283414\r\n    Hit count           = 100\r\n    Average access time = 00:00:00.0002853\r\n    Speed up factor     = 99.33894146512444\r\n\r\n  (42, 30) -> 42\r\n    Invoke duration     = 00:00:00.0315064\r\n    Hit count           = 100\r\n    Average access time = 00:00:00.0003152\r\n    Speed up factor     = 99.95685279187818\r\n\r\n  (42, 40) -> 42\r\n    Invoke duration     = 00:00:00.0480687\r\n    Hit count           = 100\r\n    Average access time = 00:00:00.0004882\r\n    Speed up factor     = 98.46108152396559\r\n\r\nSummary\r\n-------\r\n\r\n  Invocation count = 5\r\n  Access count     = 401\r\n  Trim count       = 1\r\n  Trim elapsed     = 00:00:00.0036386\r\n  Eviction count   = 1\r\n\r\n  Last eviction\r\n    Invoke duration     = 00:00:00.0223207\r\n    Hit count           = 100\r\n    Average access time = 00:00:00.0002765\r\n    Speed up factor     = 80.72585895117541\r\n\r\n\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "getValueDelayedMemoized.Delegate(43, 10);\n",
        "\n",
        "Console.WriteLine(getValueDelayedMemoized.Cache.DebugView);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Memoization caches also support direct trimming using an interface called `ITrimmable`. Different types of trimming are possible, for example based on metrics. This is illustrated in the cell below where we drop cache entries with a `HitCount` less than `10`."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "Trimmed 1 entries.\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "Entries\r\n-------\r\n\r\n  (42, 20) -> 42\r\n    Invoke duration     = 00:00:00.0283414\r\n    Hit count           = 100\r\n    Average access time = 00:00:00.0002853\r\n    Speed up factor     = 99.33894146512444\r\n\r\n  (42, 30) -> 42\r\n    Invoke duration     = 00:00:00.0315064\r\n    Hit count           = 100\r\n    Average access time = 00:00:00.0003152\r\n    Speed up factor     = 99.95685279187818\r\n\r\n  (42, 40) -> 42\r\n    Invoke duration     = 00:00:00.0480687\r\n    Hit count           = 100\r\n    Average access time = 00:00:00.0004882\r\n    Speed up factor     = 98.46108152396559\r\n\r\nSummary\r\n-------\r\n\r\n  Invocation count = 5\r\n  Access count     = 401\r\n  Trim count       = 1\r\n  Trim elapsed     = 00:00:00.0036386\r\n  Eviction count   = 1\r\n\r\n  Last eviction\r\n    Invoke duration     = 00:00:00.0223207\r\n    Hit count           = 100\r\n    Average access time = 00:00:00.0002765\r\n    Speed up factor     = 80.72585895117541\r\n\r\n\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "int trimCount = getValueDelayedMemoized.Cache.ToTrimmableByMetrics().Trim(metric => metric.HitCount < 10);\n",
        "Console.WriteLine($\"Trimmed {trimCount} entries.\");\n",
        "\n",
        "Console.WriteLine(getValueDelayedMemoized.Cache.DebugView);"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Thread safety of memoization caches\n",
        "\n",
        "By default, memoization caches returned from memoization cache factories are **not** thread-safe. This is a deliberate design choice in order to avoid overheads for single-threaded scenarios. In order to create thread-safe memoizers, one can use a few different approaches.\n",
        "\n",
        "* Use `ConcurrentMemoizationCache` instead of `MemoizationCache`.\n",
        "* Use the `Synchronized` extension method on memoization cache factories.\n",
        "* Use the `WithThreadLocal` extension method on memoization cache factories.\n",
        "\n",
        "All of these return an `IMemoizationCacheFactory` that produces caches with thread-safe behavior. Alternatively, one can memoize the same function multiple times, on different threads, and ensure that only that thread calls the memoized function.\n",
        "\n",
        "In the sample below, we use `WithThreadLocal` to cause memoization caches to be allocated on each distinct thread."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "using System.Memory;\n",
        "\n",
        "var factory = MemoizationCacheFactory.CreateLru(maxCapacity: 8).WithThreadLocal();\n",
        "\n",
        "var memoizer = Memoizer.Create(factory);\n",
        "\n",
        "var f = memoizer.Memoize((int x) =>\n",
        "{\n",
        "    Console.WriteLine($\"~{Environment.CurrentManagedThreadId} - f({x})\");\n",
        "    return x + 1;\n",
        "});"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Next, let's use the cache from two different threads. Each of them will have its own cache."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "~28 - f(1)\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "~28 - f(2)\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "Entries\r\n-------\r\n\r\n  1 -> 2\r\n    Invoke duration     = 00:00:00.0003984\r\n    Hit count           = 2\r\n    Average access time = 00:00:00.0022092\r\n    Speed up factor     = 0.18033677349266702 [DEGRADATION]\r\n\r\n  2 -> 3\r\n    Invoke duration     = 00:00:00.0001152\r\n    Hit count           = 1\r\n    Average access time = 00:00:00.0001554\r\n    Speed up factor     = 0.7413127413127413 [DEGRADATION]\r\n\r\nSummary\r\n-------\r\n\r\n  Invocation count = 2\r\n  Access count     = 3\r\n  Eviction count   = 0\r\n\r\n\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "~7 - f(1)\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "~7 - f(2)\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "Entries\r\n-------\r\n\r\n  1 -> 2\r\n    Invoke duration     = 00:00:00.0000585\r\n    Hit count           = 2\r\n    Average access time = 00:00:00.0000394\r\n    Speed up factor     = 1.484771573604061\r\n\r\n  2 -> 3\r\n    Invoke duration     = 00:00:00.0000154\r\n    Hit count           = 1\r\n    Average access time = 00:00:00.0000176\r\n    Speed up factor     = 0.875 [DEGRADATION]\r\n\r\nSummary\r\n-------\r\n\r\n  Invocation count = 2\r\n  Access count     = 3\r\n  Eviction count   = 0\r\n\r\n\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "using System.Threading;\n",
        "\n",
        "var t1 = new Thread(() =>\n",
        "{\n",
        "    f.Delegate(1);\n",
        "    f.Delegate(2);\n",
        "    f.Delegate(1); // used from thread-local cache\n",
        "\n",
        "    Console.WriteLine(f.Cache.DebugView);\n",
        "});\n",
        "t1.Start();\n",
        "t1.Join();\n",
        "\n",
        "var t2 = new Thread(() =>\n",
        "{\n",
        "    f.Delegate(1); // unique cache on this thread\n",
        "    f.Delegate(2);\n",
        "    f.Delegate(1); // used from thread-local cache\n",
        "\n",
        "    Console.WriteLine(f.Cache.DebugView);\n",
        "});\n",
        "t2.Start();\n",
        "t2.Join();"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "### Intern caches\n",
        "\n",
        "Intern caches are often used to deduplicate instances of immutable objects based on value equality. The best known sample is `string.Intern(string)` which deduplicates strings. For example, the result of calling `\"BAR\".ToLower()` can get deduplicated by `string.Intern` if an existing string with contents `\"bar\"` exists. The old copy with identical contents can then be garbage collected.\n",
        "\n",
        "Memoization caches can be used to construct intern caches, simply by memoizing an identity function `(T x) => x` using an `IEqualityComparer<T>` that checks for value equality. As an example, let's build an intern cache for `ReadOnlyCollection<T>` objects. First, we'll create an `IEqualityComparer<ReadOnlyCollection<T>>` implementation for such immutable collections, using pairwise element equality."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "using System.Collections.Generic;\n",
        "using System.Linq;\n",
        "\n",
        "class SequenceEqualityComparer<T> : IEqualityComparer<IEnumerable<T>>\n",
        "{\n",
        "    public bool Equals(IEnumerable<T> xs, IEnumerable<T> ys)\n",
        "    {\n",
        "        if (xs is null)\n",
        "        {\n",
        "            return ys is null;\n",
        "        }\n",
        "\n",
        "        if (ys is null)\n",
        "        {\n",
        "            return false;\n",
        "        }\n",
        "\n",
        "        return xs.SequenceEqual(ys);\n",
        "    }\n",
        "\n",
        "    public int GetHashCode(IEnumerable<T> xs)\n",
        "    {\n",
        "        HashCode h = new();\n",
        "\n",
        "        if (xs is not null)\n",
        "        {\n",
        "            foreach (var x in xs)\n",
        "            {\n",
        "                h.Add(x);\n",
        "            }\n",
        "        }\n",
        "\n",
        "        return h.ToHashCode();\n",
        "    }\n",
        "}"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Next, we'll create an intern cache."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [],
      "source": [
        "using System.Collections.ObjectModel;\n",
        "using System.Memory;\n",
        "\n",
        "IInternCache<ReadOnlyCollection<int>> cache = MemoizationCacheFactory.Unbounded.CreateInternCache<ReadOnlyCollection<int>>(new SequenceEqualityComparer<int>());"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Finally, we can try out our cache by instantiating multiple copies of a `ReadOnlyCollection<int>` with the same contents and running them through `Intern`."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "dotnet_interactive": {
          "language": "csharp"
        }
      },
      "outputs": [
        {
          "data": {
            "text/plain": "xs.GetHashCode() = 11261288\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "xs.GetHashCode() = 11261288 after interning\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "ys.GetHashCode() = 37913673\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        },
        {
          "data": {
            "text/plain": "ys.GetHashCode() = 11261288 after interning\r\n"
          },
          "execution_count": 1,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "var xs = new ReadOnlyCollection<int>(Enumerable.Range(0, 10).ToArray());\n",
        "\n",
        "Console.WriteLine($\"xs.GetHashCode() = {xs.GetHashCode()}\");\n",
        "\n",
        "xs = cache.Intern(xs);\n",
        "\n",
        "Console.WriteLine($\"xs.GetHashCode() = {xs.GetHashCode()} after interning\");\n",
        "\n",
        "var ys = new ReadOnlyCollection<int>(Enumerable.Range(0, 10).ToArray());\n",
        "\n",
        "Console.WriteLine($\"ys.GetHashCode() = {ys.GetHashCode()}\");\n",
        "\n",
        "ys = cache.Intern(ys);\n",
        "\n",
        "Console.WriteLine($\"ys.GetHashCode() = {ys.GetHashCode()} after interning\");"
      ]
    }
  ],
  "metadata": {
    "kernelspec": {
      "display_name": ".NET (C#)",
      "language": "C#",
      "name": ".net-csharp"
    },
    "language_info": {
      "file_extension": ".cs",
      "mimetype": "text/x-csharp",
      "name": "C#",
      "pygments_lexer": "csharp",
      "version": "9.0"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 4
}